1. Field of the Invention
The present invention relates to wireless communication systems, and more particularly, to a method and apparatus for the management of authentication keys (A-keys) which are used to authenticate mobile stations in a cellular radio system.
2. Related Prior Art Systems
The prior art includes cellular radio systems which have been operating in the United States since the early 1980s, and providing telephone service to an ever growing subscriber base, presently estimated at over 20 million subscribers. Cellular telephone service operates much like the fixed, wireline telephone service in homes and offices, except that radio frequencies rather than telephone wires are used to connect telephone calls to and from the mobile subscribers. Each mobile subscriber is assigned a private (10 digit) directory telephone number and is usually billed based on the amount of "airtime" he or she spends talking on the cellular telephone each month. Many of the service features available to landline telephone users (e.g., call waiting, call forwarding, three-way calling, etc.) are also generally available to mobile subscribers.
In the United States, cellular licenses have been awarded by the Federal Communications Commission (FCC) pursuant to a licensing scheme which divided the country into geographic service markets defined according to the 1980 Census. Only two cellular licenses are awarded for each market. The two cellular systems in each market are commonly referred to as the "A" system and "B" system, respectively. Each of the two systems is allocated a different frequency block in the 800 MHz band (called the A-band and B-band, respectively). To date, the FCC has released a total of 50 Mhz for cellular services (25 MHz per system). Mobile subscribers have the freedom to subscribe to service from either the A-system or the B-system operator (or both). Each system will assign each of its own subscribers a mobile identification number (MIN). The local system from which service is subscribed is called the "home" system. When travelling outside the home system, a mobile subscriber may be able to obtain service in a distant system if there is a "roaming" agreement between the operators of the home and "visited" systems.
The architecture for a typical cellular radio system is shown in FIG. 1. A geographical area (e.g., a metropolitan area) is divided into several smaller, contiguous radio coverage areas, called "cells," such as cells C1-C10. The cells C1-C10 are served by a corresponding group of fixed radio stations, called "base stations," B1-B10, each of which includes a plurality of RF channel units (transceivers) that operate on a subset of the RF channels assigned to the system, as well known in the art. For illustration purposes, the base stations B1-B10 are shown in FIG. 1 to be located at the center of the cells C1-C10, respectively, and are shown to be equipped with omni-directional antennas transmitting equally in all directions. However, the base stations B1-B10 may also be located near the periphery or otherwise away from the centers of the cells C1-C10, and may illuminate the cells C1-C10 with radio signals directionally (e.g., a base station may be equipped with three directional antennas each covering a 120 degrees sector).
The RF channels allocated to any given cell (or sector) may be reallocated to a distant cell in accordance with a frequency reuse plan as is well known in the art. In each cell (or sector), at least one RF channel is used to carry control or supervisory messages, and is called the "control" or "paging/access" channel. The other RF channels are used to carry voice conversations, and are called the "voice" or "speech" channels. The cellular telephone users (mobile subscribers) in the cells C1-C10 are provided with portable (hand-held), transportable (hand-carried) or mobile (car-mounted) telephone units, collectively referred to as "mobile stations," such as mobile stations M1-M5, each of which communicates with a nearby base station. Each of the mobile stations M1-M5 includes a controller (microprocessor) and a transceiver, as well known in the art. The transceiver in each mobile station may tune to any of the RF channels specified in the system (whereas each of the transceivers in the base stations B1-B10 usually operates on only one of the different RF channels used in the corresponding cell).
With continuing reference to FIG. 1, the base stations B1-B10 are connected to and controlled by a mobile telephone switching office (MTSO) 20. The MTSO 20, in turn, is connected to a central office (not specifically shown in FIG. 1) in the landline (wireline) public switched telephone network (PSTN) 30, or to a similar facility such as an integrated system digital network (ISDN). The MTSO 20 switches calls between wireline and mobile subscribers, controls signalling to the mobile stations M1-M5, compiles billing statistics, stores subscriber service profiles, and provides for the operation, maintenance and testing of the system.
When turned on (powered up), each of the mobile stations M1-M5 enters the idle state (standby mode) and tunes to and continuously monitors the strongest control channel (generally, the control channel of the cell in which the mobile station is located at that moment). When moving between cells while in the idle state, the mobile station will eventually "lose" radio connection on the control channel of the "old" cell and tune to the control channel of the "new" cell. The initial tuning to, and the change of, control channel are both accomplished automatically by scanning all the control channels in operation in the cellular system to find the "best" control channel (in the United States, there are 21 "dedicated" control channels in each cellular system which means that the mobile station has to scan a maximum number of 21 RF channels). When a control channel with good reception quality is found, the mobile station remains tuned to this channel until the quality deteriorates again. In this manner, the mobile station remains "in touch" with the system and may receive or initiate a telephone call through one of the base stations B1-B10 which is connected to the MTSO 20.
To detect incoming calls, the mobile station continuously monitors the current control channel to determine whether a page message addressed to it (i.e., containing its MIN) has been received. A page message will be sent to the mobile station, for example, when an ordinary (landline) subscriber calls the mobile subscriber. The call is directed from the PSTN 30 to the MTSO 20 where the dialed number is analyzed. If the dialed number is validated, the MTSO 20 requests some or all of the base stations B1-B10 to page the called mobile station throughout their corresponding cells C1-C10. Each of the base stations B1-B10 which receive the request from the MTSO 20 will then transmit over the control channel of the corresponding cell a page message containing the MIN of the called mobile station. Each of the idle mobile stations M1-M5 which is present in that cell will compare the MIN in the page message received over the control channel with the MIN stored in the mobile station. The called mobile station with the matching MIN will automatically transmit a page response over the control channel to the base station, which then forwards the page response to the MTSO 20. Upon receiving the page response, the MTSO 20 selects an available voice channel in the cell from which the page response was received (the MTSO 20 maintains an idle channel list for this purpose), and requests the base station in that cell to order the mobile station via the control channel to tune to the selected voice channel. A through-connection is established once the mobile station has tuned to the selected voice channel.
When, on the other hand, a mobile subscriber initiates a call (e.g., by dialing the telephone number of an ordinary subscriber and pressing the "send" button on the telephone handset in the mobile station), the dialed number and MIN/ESN pair for the mobile station are sent over the control channel to the base station and forwarded to the MTSO 20, which validates the mobile station, assigns a voice channel and establishes a through-connection for the conversation as described before. If the mobile station moves between cells while in the conversation state, the MTSO 20 will perform a "handoff" of the call from the old base station to the new base station. The MTSO 20 selects an available voice channel in the new cell and then orders the old base station to send to the mobile station on the current voice channel in the old cell a handoff message which informs the mobile station to tune to the selected voice channel in the new cell. The handoff message is sent in a "blank and burst" mode which causes a short but hardly noticeable break in the conversation. Upon receipt of the handoff message, the mobile station tunes to the new voice channel and a through-connection is established by the MTSO 20 via the new cell. The old voice channel in the old cell is marked idle in the MTSO 20 and may be used for another conversation. Furthermore, when travelling outside the system, the mobile station may be handed off to a cell in an adjacent system if there is a roamning agreement between the operators of the two systems.
In order to properly direct incoming calls to a mobile station which is moving around between different cells or systems, it is necessary to keep track of the location and activity of the mobile station. For this purpose, an autonomous registration process has been used in which the mobile station sends a registration message to the system upon entering a new system area or a new location area (i.e., a predefined group of cells in the system), or at predetermined intervals defined by the system operator. The system area and location area registration functions can be used to identify the current location of the mobile station so that it can be paged in its actual (or most likely) location rather than in all locations in the system. Each time the system receives a registration message from a mobile station in its area, it marks this mobile station as being active and present in its system area, or in the particular location area containing the cell of the base station which received the registration message, and then sends a registration confirmation message to this mobile station. The periodic registration function, on the other hand, is used to determine whether a mobile station is active (powered and within radio range) in a cellular system. Incoming calls to inactive mobile stations can be routed immediately to a recorded message (e.g., "The mobile customer you have called has turned off the mobile unit or travelled out of the service area.") without ever paging these mobile stations. This reduces the paging load and results in more efficient use of the limited control channel capacity.
The primary parameters that regulate the various mobile registration functions include the next registration (NXTREG) value which is stored in each mobile station and the system identification (SID), location area identification (LOCAID), registration identification (REGID) and registration increment (REGINCR) values which are broadcast by the system on the control channel of each cell. The SID is a digital number which uniquely identifies the serving cellular system. The LOCAID is a digital number which identifies a particular location area comprised of one or more cells in the system. The REGINCR defines the length of the periodic registration interval. The REGID is a 20-bit counter that is stepped by one unit in every REGID message transmitted to the mobile station. The NXTREG value indicates when periodic registration is due and is calculated internally in the mobile station by adding the current values of REGID and REGINCR. A mobile station will register with the serving system if either the SID or LOCAID received over the control channel is different from the corresponding value which it stored the last time it received a registration confirmation message (thus implying that the mobile station has travelled to a new system or location area, respectively), or if the REGID value received over the control channel is greater than or equal to the stored NXTREG (thus implying that a periodic registration is due). The mobile station updates the NXTREG value (with the sum of the current REGID and REGINCR values) upon the receipt of each registration confirmation message and, also, after every successful voice channel designation (i.e., call originations and receptions are treated like normal periodic registrations since by making or receiving a call a mobile station shows its activity and location).
Access to the cellular system of FIG. 1 by any of the mobile stations M1-M5, whether for call origination or reception or for registration purposes, is controlled on the basis of a mobile identification number (MIN) and an electronic serial number (ESN) which are stored in the mobile station. The MIN identifies the service subscription and is a binary representation of the 10-digit directory telephone number of the mobile subscriber. The MIN is assigned by the cellular service provider (home system operator) and is usually programmed into a mobile station either when purchased by the original user or when sold to another user (i.e., at the time of service installation). The MINs of legitimate (paying) subscribers are stored by the MTSO 20. The ESN uniquely identifies the mobile station and is a digital number which is supplied by the manufacturer and permanently stored in the mobile station (i.e., factory-set, not to be altered in the field). The ESNs of mobile stations which have been reported to be stolen can be appropriately marked by the MTSO 20 and denied service permanently.
Besides the MIN and ESN, each mobile station is also identified by a station class mark (SCM) which designates the transmit power class, mode and bandwidth for the mobile station. Mobile stations in different power classes (portable, transportable or vehicular) will transmit at one of several specified power levels within different output power ranges (0.6, 1.6 or 4.0 Watts). The transmit power level within a given range can be increased or decreased by a power change command from the base station. Furthermore, some mobile stations have the ability to operate in a "discontinuous" transmission (DTX) mode in which they can switch autonomously between two transmitter power level states ("DTX high" and "DTX low"). In addition, some mobile stations are set to operate within only the "basic" frequency range initially allocated to cellular systems while others are also set to operate in the "extended" frequency range which was later allocated. Like the MIN and ESN, the relevant SCM information is stored in each mobile station.
User authorization for cellular service is usually performed at every system access (i.e., registration request, call origination or page response) by a mobile station. When making an access, the mobile station forwards the MIN, ESN and SCM to the system. The MTSO 20 maintains a "white list" containing the MIN/ESN pairs of valid home subscribers and a "black list" containing the ESNs of stolen or otherwise unauthorized mobile stations. The MTSO 20 checks the received MIN/ESN pair to determine whether it belongs to a valid home subscriber and, if not, whether the MIN belongs to an authorized "roamer" from another system and whether the ESN has been blacklisted. If the MIN/ESN pair is not valid, or if the MIN is not recognized or if the ESN is blacklisted, the mobile station may be denied access. Otherwise, the user is considered legitimate and the access is accepted. Service is then provided and controlled according to the received SCM information.
The original cellular radio systems, as described generally above, used analog transmission methods, specifically frequency modulation (FM), and duplex (two-way) RF channels in accordance with the Advanced Mobile Phone Service (AMPS) standard. According to the AMPS standard, each control or voice channel between the base station and the mobile station uses a pair of separate frequencies consisting of a forward (downlink) frequency for transmission by the base station (reception by the mobile station) and a reverse (uplink) frequency for transmission by the mobile station (reception by the base station). The AMPS system, therefore, is a single-channel-per-carrier (SCPC) system allowing for only one voice circuit (telephone conversation) per RF channel. Different users are provided access to the same set of RF channels with each user being assigned a different RF channel (pair of frequencies) in a technique known as frequency division multiple access (FDMA). This original AMPS (analog) architecture forms the basis for an industry standard sponsored by the Electronics Industries Association (EIA) and the Telecommunication Industry Association (TIA), and known as EIA/TIA-553.
In the late 1980s, however, the cellular industry in the United States began migrating from analog to digital technology, motivated in large part by the need to address the steady growth in the subscriber population and the increasing demand on system capacity. It was recognized early on that the capacity improvements sought for the next generation cellular systems could be achieved by either "cell splitting" to provide more channels per subscribers in the specific areas where increased capacity is needed, or by the use of more advanced digital radio technology in those areas, or by a combination of both approaches. According to the first approach (cell splitting), by reducing the transmit power of the base station, the size of the corresponding cell (or cell radius) and, with it, the frequency reuse distance are reduced thereby resulting in more channels per geographic area (i.e., increased capacity). Additional benefits of a smaller cell include a longer "talk time" for the user since the mobile station will use substantially lower transmit power than in a larger cell and, consequently, its battery will not need to be recharged as often.
While cell splitting held the promise of improving both capacity and coverage for the growing mobile subscriber base, the actual capacity gains were limited by the use of the analog AMPS technology. It was commonly believed that the desired capacity gains, and indeed the effectiveness of the microcellular (cell splitting) concept in increasing capacity, can be maximized only by the use of digital technology. Thus, in an effort to go digital, the EIA/TIA developed a number of air interface standards which use digital voice encoding (analog-to-digital conversion and voice compression) and time division multiple access (TDMA) or code division multiple access (CDMA) techniques to multiply the number of voice circuits (conversations) per RF channel (i.e., to increase capacity). These standards include IS-54 (TDMA) and IS-95 (CDMA), both of which are "dual mode" standards in that they support the use of the original AMPS analog voice and control channels in addition to digital speech channels defined within the existing AMPS framework (so as to ease the transition from analog to digital and to allow the continued use of existing analog mobile stations). The dual-mode IS-54 standard, in particular, has become known as the digital AMPS (D-AMPS) standard. More recently, the EIA/TIA has developed a new specification for D-AMPS, which includes a digital control channel suitable for supporting public or private microcell operation, extended mobile station battery life, and enhanced end-user features. This new specification builds on the IS-54B standard (the current revision of IS-54), and it is known as IS-136. (All of the foregoing EIA/TIA standards are hereby incorporated herein by reference as may be necessary for a full understanding of these background developments. Copies of these standards may be obtained from the Electronics Industries Association, 2001 Pennsylvania Avenue, N.W., Washington, D.C. 20006).
In addition to providing for a new, digital radio transmission format, each of IS-54B and IS-136 specifies an authentication procedure for confirming the identity of mobile stations demanding service in a cellular system. This procedure, which also has been imported into newer analog standards such as IS-91 for narrowband AMPS (N-AMPS) and Revision A of EIA/TIA-553 (EIA/TIA-553A currently under development), was developed in response to the widespread, fraudulent use of MIN/ESN pairs to steal cellular service from existing analog systems. Many of the mobile stations which have been sold to date do not comply with the tamper-proof requirement for ESN and, consequently, can be easily programmed with a new ESN (there is no tamperproof requirement for MIN and, hence, all mobile stations are easily programmed with a new MIN). Thus, these mobile stations can be programmed to transmit any MIN/ESN pair so as to "trick" the system into granting access. Further background on this MIN/ESN "tumbling" and the resultant revenue and service losses can be found in the article entitled "Cellular Fraud" by Henry M. Kowalczyk, in Cellular Business, dated March 1991, at pp. 32-35.
Fraud in the form of MIN/ESN tumbling arose primarily in a "manual roaming" environment where the cellular systems were not interconnected on a real-time basis. Since each MTSO usually contained a list only of valid MIN/ESN pairs belonging to the home subscribers, it did not have immediate access to the counterpart lists in the other systems. Hence, by using a roamer MIN (i.e., a 10-digit directory telephone number containing an area code other than the local area code of the home system operator) and a non-blacklisted ESN, a fraudulent mobile station could receive service from the local cellular system until an indication of the invalidity of the MIN/ESN pair has been received (perhaps hours later) from the home system of the pretending roamer (or from a clearing house). In an "automatic roaming" environment, however, the cellular systems are networked together on a real-time basis in accordance with the provisions of the EIA/TIA standard IS-41 (or through a proprietary signalling protocol). Consequently, the serving cellular system can obtain verification of a MIN/ESN pair from the home system virtually immediately and can, therefore, deny service to a MIN/ESN tumbler without significant delay.
Of more concern recently has been a type of fraud known as "cloning" in which a fraudulent user adopts the bona fide MIN/ESN pair of a valid (paying) subscriber. The fraudulent user may surreptitiously acquire a bona fide MIN/ESN pair, or even a list of valid MIN/ESN pairs, in several ways. For example, in some instances, bona fide MIN/ESN numbers are printed on, and may be read from, a label which is affixed to a mobile station belonging to a valid subscriber. In other instances, a list of bona fide MIN/ESN pairs may be purchased on the "black market" or directly from an employee of the cellular operator. In addition, since each mobile station transmits the MIN/ESN pair to the serving exchange at every system access, one or more bona fide MIN/ESN pairs may be intercepted by listening to radio transmissions on the (analog) control channel.
The authentication procedures in the newer industry standards seek to distinguish between legitimate mobile stations and fraudulent clones through the synchronized generation of cryptovariables from identical sets of shared secret data (SSD) which are stored and periodically updated in a mobile station and its serving base station. These cryptovariables are exchanged between the mobile station and the base station for the purpose of confirming the identity of the mobile station. Since a clone mobile station is assumed not to have access to the initial value of the SSD or the subsequent history of SSD updates in the legitimate mobile station, its cryptovariables will not match those of the base station and therefore it can be identified as a clone. The SSD for each mobile station is stored in the MTSO of the home system, or in a separate subscriber database called a "home location register" (HLR) which is connected to that MTSO, and provided to the serving base station. Each mobile station also stores its SSD in memory.
In the process of authentication, the base station generates and sends to the mobile station a random bit pattern, called RAND or RANDU, on the analog control channel (ACCH), digital control channel (DCCH), analog voice channel (AVCH) or digital traffic channel (DTCH). Each of the mobile station and the base station uses RAND or RANDU, a portion of SSD called SSD-A (the remaining portion, SSD-B, is used for encryption, and not for authentication), along with other parameters (e.g., the MIN and ESN of the mobile station) as inputs to a Cellular Authentication and Voice Encryption (CAVE) algorithm, which is defined in Appendix A to each of IS-54B and IS-136, to generate an authentication response called AUTHR or AUTHU (depending on whether RAND or RANDU is used, respectively). The authentication response computed in the mobile station is sent to the base station to be compared with the authentication response computed in the base station. If the authentication responses match, authentication is considered successful (i.e., the base station and the mobile station are considered to have identical sets of SSD). However, if the comparison at the base station fails, the base station may deny service to the mobile station or commence the process of updating the SSD.
The procedure for updating SSD for any mobile station involves the application of CAVE initialized with mobile station-specific information (ESN), certain random data (RANDSSD), and a secret, permanent authentication key (A-key) which is uniquely assigned to the mobile station. For security reasons, the A-key is never transmitted over the air interface between the base station and the mobile station, or over the network interface between different cellular systems. The A-key is stored in the MTSO or the HLR and must be entered into the memory of the mobile station for use in updating the SSD. The A-key can be entered into the mobile station at the time of mobile service activation by an authorized technician using the standard number assignment module (NAM) programming mode, or at any time by the mobile subscriber using a separate Akey programming mode as disclosed in U.S. Pat. No. 5,551,073, which is incorporated herein by reference. For any mobile stations which have multiple NAMs and use multiple MINs (i.e., where the user subscribes to service from multiple home systems in order to avoid roamer charges in those systems), multiple A-keys may have to be entered into the mobile station, one for each NAM (MIN). A different A-key should be entered for each MIN since, for security reasons, the A-key can be known only to the mobile station and the MTSO or HLR of the home system, and should not be passed from system to system as the mobile station roams. Thus, SSD updates (in which the A-key is used to generate new SSD values) are carried out only in the mobile station and its associated home system MTSO or HLR, which then sends the SSD values (but not the A-key) to the serving system.
Because of the importance of the A-key for authentication purposes, the issue of A-key security management has been of concern to the industry. It was originally envisioned that each mobile station would be shipped from the factory with a default A-key consisting of all binary zeros and that an operational value for the A-key would be assigned by the system operator when a mobile subscriber signed up for service. The assigned A-key value then would be entered by the service technician or the user. However, because of the administrative burden and the security risk associated with the delivery (e.g., through the post) of numerous A-keys to service technicians or mobile subscribers, it was deemed more preferable that the manufacturers of the mobile stations would ship each of the mobile stations with a random A-key value. Any manufacturer then could provide any system operator with a list of ESN/random A-key combinations in a secure database, for example. The A-key values from this list, in turn, would be programmed into the home system MTSO or HLR and used by the system operator for authenticating the corresponding mobile stations.
At present and for the foreseeable future both of the foregoing approaches to A-key management (default A-key and random A-key) have been and are expected to be used in the cellular industry. The default A-key approach is followed by some operators because of its simplicity and/or because of the inability of some MTSOs to be programmed with specific A-key values (random or otherwise) for all of the various subscribers. A few of these operators have even resorted to resetting the A-key to the default value in all cases, including those in which the A-key may have been initially set to a random value. Other operators, however, prefer to use the random A-key approach because of its added security. Still other operators who seek additional security recognize that an ESN/random A-key list can become excessive, unmanageable or corrupted, and that for multiple NAM mobile stations the same random A-key will be available to multiple carriers thus compromising security (unless the manufacturer is willing to program different random A-key values for the different NAMs in which case the ESN/A-Key list may become even larger). Such operators may prefer to have an individual (custom) A-key assigned to the mobile subscriber at the time of service activation for entry into his mobile station.
Given this background and the proclivity of some subscribers to switch between different service providers (operators) possibly having different A-key management policies, there is a need for an A-key management procedure which integrates the existing approaches, while at the same time avoiding their shortcomings such as the cost of maintaining lists of random A-keys for the mobile stations from each manufacturer.